With a message authentication algorithm, when messages are exchanged between two parties, a recipient can confirm whether or not a sent message has been tampered with.
When tampering is to be detected using the message authentication algorithm, a key K is shared by the two parties in advance. The sender of the message generates an authenticator T for a message M from the message M and the key K, and sends the message M and the authenticator T to the recipient. The recipient of the message generates an authenticator T′ from the received message M and the key K. If the received authenticator T and the generated authenticator T′ agree, the recipient judges that the message M has not been tampered with. If the authenticator T and the authenticator. T′ do not agree, the recipient judges that the message has been tampered with.
The security of the message authentication algorithm is expressed by the indistinguishability from a random function.
Assume that a message authentication algorithm F satisfies the indistinguishability. This means that, considering a distinguisher D who interacts with either the real world or the ideal world, which world the distinguisher D interacts with cannot be guessed.
In the real world, the key K is randomly chosen, and the distinguisher D can choose the message M and obtain a message authenticator of F(K, M). In the ideal world, for a random function R, the distinguisher D can choose the message M and obtain an output value of R(M). Here, the distinguisher D can choose the message M as often as he or she wishes, and can obtain an output value of F(K, M) or R(M) corresponding to the chosen message M.
More precisely, consider a distinguisher D who outputs a 1-bit value. The indistinguishability of the message authentication algorithm F is assessed from the difference between the probability that the distinguisher D outputs 1 in the real world and the probability that the distinguisher D outputs 1 in the ideal world.
The distinguisher D can obtain a plurality of outputs from the message authentication algorithm F in the real world, and can obtain a plurality of outputs from the random function R in the ideal world. In this case, if the difference between the above-mentioned probabilities is equal to or or less than p for any distinguisher D and p is a negligibly small value, the message authentication algorithm F satisfies the indistinguishability. This p is called distinction probability.
A block cipher E, taking as input a k-bit key K and an n-bit plaintext m, outputs an n-bit ciphertext c. That is, c=E(K, m). Note that k n hereinbelow. The block cipher E is a substitution function having an n-bit input/output length if the key is fixed.
Non-Patent Literatures 4 to 6 describe block cipher.
There is a block-cipher based message authentication algorithm. With the block-cipher based message authentication algorithm, a message M is divided into message blocks at every n bits, and block cipher calculation is carried out for each divided message block.
The efficiency of the block-cipher based message authentication algorithm is influenced by the number of calls, the parallelism, and the key size explained below.
The number of calls: The efficiency changes depending on how many times the block cipher is called in order to calculate the n-bit message block. When the block cipher is to be called x times for the n-bit message block, 1/x is called a rate. The closer to 1 the rate is, the smaller the number of block cipher calls, providing a high efficiency.
Parallelism: Where parallel algorithm processing is possible, the calculation time can be shortened by performing computations by hardware or a multicore in a parallel manner, providing a high efficiency.
Key size: The key size of the message authentication algorithm changes depending on how many inner block-cipher keys are employed. The key size is the smallest when only one block cipher key K is employed, that is, when the processing is performed using only one k-bit key K.
In assessing the distinction probability of the block-cipher based message authentication algorithm, it is supposed that the block cipher is an ideal block cipher, or a block cipher E(K, ·) with the key K being fixed is a random substitution.
The distinction probability p is obtained from a size n being the bit count of the ciphertext c of the block cipher E, the number q of outputs from the message authentication algorithm available to the distinguisher D, and a value bmax obtained by dividing the maximum length of the input message to the message algorithm by n. Where the maximum length of the input message is expressed as lmax in bit, bmax=lmax/n. The security of the message authentication algorithm is assessed from the value of bmax×q with which p=1. The larger the value of bmax×q, the more secure the algorithm is.
Non-Patent Literatures 1 and 2 each describe a block-cipher based message authentication algorithm which has a k-bit key-size, is parallel-processing possible, and provides a rate of 1.
It is indicated that the message authentication algorithm described in Non-Patent Literature 1 provides p=(bmax×q)2/2n if the block cipher E with the key K being fixed is replaced by a random substitution. That is, if bmax×q=2n/2, p=1.
Non-Patent Literature 3 describes a block-cipher based message authentication algorithm whose security is improved over Non-Patent Literatures 1 and 2. The message authentication algorithm described in Non-Patent Literature 3 employs 3 (three) k-bit keys, and thus has a 3 k-bit key size, is parallel-processing possible, and provides a rate of 1.
It is indicated that the message authentication algorithm described in Non-Patent Literature 3 provides p=(bmax×q)3/22n if the block cipher E with the key K being fixed is replaced by a random substitution. That is, if bmax×q=22n/3, p=1.